Using classifiers in the technical literature, the learning and classification (or recognition) tasks require the essential step of processing input patterns. During the learning phase, this step is performed to define whether or not the input pattern needs to be learned in the classifier. During the classification phase, for instance, in the K Nearest Neighbor (KNN) mode, when a new input pattern is presented to the classifier, this step is used to find the closest pattern(s) stored in the ANN as prototype(s). Finding the closest stored prototype(s) mainly consists to compute the distances between the input pattern and the stored prototypes and then, to determine the minimum distance(s) among the computed distances. In the following description, the preferred classifier is the input space mapping algorithm based artificial neural network (ANN) described in U.S. Pat. No. 5,621,863 assigned to IBM Corp that includes innovative elementary processors of a new type, referred to as the ZISC neurons, (ZISC is a registered trade mark of IBM Corp). An essential characteristic of the ZISC neurons (now commercially available in silicon chips) lies in their ability to work in parallel, i.e. when an input pattern is presented to the ANN, all ZISC neurons compute the distance between the input pattern and all the prototypes stored in the neurons of the ANN at the same time. One important aspect of these algorithms is the distance evaluation relation, referred to as the “norm”, that is used in the distance evaluation process. The choice of this norm is determined by the problem to be solved on the one hand, and on the other hand by the knowledge used to solve this problem. In a ZISC neuron, the final distance (Dist) between an input pattern A and the prototype B stored therein (each having p components) is calculated using either the MANHATTAN distance (L1 norm), i.e. DistL1=Σ|Ai−Bi| or the MAXIMUM distance (Lsup norm), i.e. DistLsup=max|Ai−Bi| wherein Ai and Bi are the components of rank i (variable i varies from 1 to p) for the input pattern A and the stored prototype B respectively. Other norms exist, for instance the L2 norm such as DistL2√{square root over (Σ(Ai−Bi)2)}. The L2 norm is said to be “Euclidean” while the L1 and Lsup norms are examples of “non-Euclidean” norms, however, they all imply the computation of a difference (Ai−Bi) for each component in the distance evaluation. In the ZISC neuron, the choice between the L1 or Lsup norm is determined by the value of a single bit referred to as the “norm” bit No stored in the neuron. Other Euclidean or non-Euclidean norms are known for those skilled in the art.
In many applications based on these input space mapping based algorithms, for instance in signal and image processing, the mail step consists in analyzing an essential characteristic of the input patterns. Although a determined input pattern and the prototypes stored in the ANN can be similar (or even identical) as far as this essential characteristic is concerned, the distance therebetween may be high due to the other parameters taken into consideration in the distance evaluation process. As a consequence, it is often necessary to use as may neurons as there are different variations in the input patters to store them as different prototypes. The two examples described below will illustrate this major inconvenience.
Let us first consider two input patterns which are electrical signals S1 and S2, each representing a voltage amplitude varying as a function of time i.e. V=f(t) in a range between a minimum value (Vmin) and a maximum value (Vmax). As apparent in FIG. 1, in the interval [t0,t1] defined by times t0 and t1, the curves depicting signals S1 and S2 have the same aspect. This common characteristic will be referred to hereinbelow as a “shape”. They exhibit the same variation, because they have the same gradient in absolute value and sign, but they are centered around two different mean values. The mean value is thus the parameter which distinguishes the two signals S1 and S2 in the time interval in consideration. In the instant case, let us assume the voltage range (from Vmin to Vmax) is coded on 8 bits with 16 points of sampling. In this time interval, assuming Vmin=0 and Vmax=255, signals S1 and S2 are respectively represented by the values given in tables T1 and T2 after sampling and coding. In the FIG. 1 case, because the amplitude values of signals S1 and S2 are different, two neurons having at least 16 components are required to store signals S1 and S2 as two different prototypes in the learning phase even if their variations look similar on the totality of the time interval. On the other hand, in the classification phase, when an input pattern is presented to the ANN for classification, e.g. signal S3 (corresponding values are given in table T3) placed between signals S1 and S2 and having the same variation in said time interval but a different mean value, it could be not recognized as close (i.e. similar) to either signal S1 or S2.
Now, let us consider the case where the input patterns are two sub-images I1 and I2 globally having a similar aspect as shown in FIG. 2. Images I1 and I2, that are comprised of three stripes of twelve pixels (for a total of 36 pixels), slightly distinguishes one from another, in fact, they only differ in terms of global brightness. In the instant case, the brightness of each pixel of sub-images I1 and I2 is coded on 8 bits to have a coding values ranging from 0 (black) to 255 (white) with all the permitted gray levels therebetween. The result of this coding is illustrated by tables T′1 and T′2. As apparent in tables T′1 and T′2, sub-images I1 and I2 have the same brightness gradient, giving them said similar aspect mentioned above and this common characteristic will still be referred to hereinbelow as a “shape”. As described above, because the brightness values of the pixels of sub-images I1 and I2 are different, two neurons having the capability to memorize 36 components (corresponding to the 36 coding values of either table which characterize the brightness of a sub-image) are required to store these two sub-images as prototypes during the learning phase even if they have the same shape.
In conclusion, it is thus often necessary to use as many neurons as there are possible variations of a same shape. These variations being defined by at least one parameter (in the two above described examples in terms of mean value or of brightness respectively) of a same shape.
Of course, the problem described above by reference to FIGS. 1 and 2 can be generalized to input patterns having dimensions greater than one (see FIG. 1) or two (see FIG. 2).
The number of neurons is not unlimited in conventional ANNs, so that, when several neurons are required to memorize a same shape, it results a significant waste of the capacity of the ANN to store prototypes and finally, less different shapes can be stored therein. Finally, using several neurons to memorize a same shape decreases the ANN response quality.
Therefore, requiring as many stored prototypes, i.e. neurons, as there are possible variations of a same shape is thus a major inconvenience in conventional ANNs.